HDOJ 2066 【Dijkstra】一个人的旅行

【题目描述】

http://acm.hdu.edu.cn/showproblem.php?pid=2066

【思路】

看起来是多源多终点的最短路问题，每个起点和每个终点都枚举的话，复杂度会很高，所以我自己建一个点，编号是0，在它与所有的起点之间建一条费用为0的双向边，再建一个点，编号是2000（远大于数据范围），在它和所有的终点之间建0费用边。
然后问题就很好解决了，单源最短路嘿！(:з」∠)

Dijkstra+heap+前向星：

#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

const int Max=21000000;
typedef pair<int,int> Pair;
priority_queue< Pair, vector<Pair>, greater<Pair> > Q;

int dis[2100],head[2100];
int tail;

struct data
{
      int w,to,next;
}edge[201000],k;

void build(int a,int b,int x)
{
      edge[tail].w=x;
      edge[tail].to=b;
      edge[tail].next=head[a];
      head[a]=tail++;
}

void Dijkstra()
{
      Pair s,u;
      int v,val;

      dis[0]=0;
      s.first=0;
      s.second=0;
      Q.push(s);

      while (!Q.empty())
      {
            u=Q.top();
            Q.pop();
            val=u.first;
            v=u.second;
            if (dis[v]<val) continue;

            for (int i=head[v]; i!=-1; i=edge[i].next)
            {
                  k=edge[i];
                  if (dis[k.to]>dis[v]+k.w)
                  {
                        dis[k.to]=dis[v]+k.w;
                        Q.push(Pair(dis[k.to],k.to));
                  }
            }
      }
}

int main()
{
      int T,S,D,a,b,x;

      while (scanf("%d%d%d",&T,&S,&D)!=EOF)
      {
            for (int i=0;i<2100;i++) head[i]=-1;
            for (int i=0;i<2100;i++) dis[i]=Max;
            tail=0;

            for (int i=1;i<=T;i++)
            {
                  scanf("%d%d%d",&a,&b,&x);
                  build(a,b,x);
                  build(b,a,x);
            }
            for (int i=1;i<=S;i++)
            {
                  scanf("%d",&x);
                  build(0,x,0);
                  build(x,0,0);
            }
            for (int i=1;i<=D;i++)
            {
                  scanf("%d",&x);
                  build(2000,x,0);
                  build(x,2000,0);
            }
            Dijkstra();
            printf("%d\n",dis[2000]);
      }

      return 0;
}